// 2025/07/27
// Author: Forever
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;
int n, m, a[MAXN], c[MAXN], ans[MAXN], last_pos[MAXN];
#define lowbit(x) (x & -x)

inline void add(int x, int v)
{
    while (x <= n)
        c[x] += v, x += lowbit(x);
}

inline int sum(int x, int y)
{
    x--;
    int res1 = 0, res2 = 0;
    while (x)
        res1 += c[x], x -= lowbit(x);
    while (y)
        res2 += c[y], y -= lowbit(y);
    return res2 - res1;
}

struct input {
    int l, r, id;
} q[MAXN];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, [](input a, input b) { return a.r < b.r; });
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        if (last_pos[a[i]])
            add(last_pos[a[i]], -1);
        last_pos[a[i]] = i;
        add(i, 1);
        while (cnt <= m && q[cnt].r == i) {
            ans[q[cnt].id] = sum(q[cnt].l, q[cnt].r);
            cnt++;
        }
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";
    return 0;
}